package main.LeetCode75.Level2;

import java.util.*;

public class Day1_Day5 {
    public static void main(String[] args) {
        System.out.println("**************************Day1**************************");
        System.out.println("Question202：快乐数");
        System.out.println("Question54：螺旋矩阵");
        System.out.println("Question1706：球会落何处");
        System.out.println("**************************Day2**************************");
        System.out.println("Question14：最长公共前缀");
        System.out.println("Question43：字符串相乘");
        System.out.println("**************************Day3**************************");
        System.out.println("Question19：删除链表的倒数第 N 个结点");
        System.out.println("Question234：回文链表");
        System.out.println("**************************Day4**************************");
        System.out.println("Question328：奇偶链表");
        System.out.println("Question148：排序链表");
        System.out.println("**************************Day5**************************");
        System.out.println("Question2131：连接两字母单词得到的最长回文串");
        System.out.println("Question621：任务调度器");
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Question202{
    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = getNext(n);
        }
        return n == 1;
    }
    public int getNext(int n){
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }
}

class Question54{
    public void process(int[][] mat, int leftRow, int leftCol, int rightRow, int rightCol, List<Integer> list) {
        if (rightRow < leftRow || rightCol < leftCol) return;
        if (leftRow == rightRow) {// 只有一行时，按「行」遍历
            for (int i = leftCol; i <= rightCol; i++) list.add(mat[leftRow][i]);
            return;
        }
        if (leftCol == rightCol) {// 只有一列时，按「列」遍历
            for (int i = leftRow; i <= rightRow; i++) list.add(mat[i][rightCol]);
            return;
        }
        for (int i = leftCol; i < rightCol; i++) list.add(mat[leftRow][i]);//上行
        for (int i = leftRow; i < rightRow; i++) list.add(mat[i][rightCol]);//右列
        for (int i = rightCol; i > leftCol; i--) list.add(mat[rightRow][i]);//下行
        for (int i = rightRow; i > leftRow; i--) list.add(mat[i][leftCol]);//左列
        process(mat, leftRow + 1, leftCol + 1, rightRow - 1, rightCol - 1, list);//遍历下层
    }
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list=new ArrayList<>();
        int leftRow=0,leftCol=0,rightRow= matrix.length-1,rightCol=matrix[0].length-1;//定义左上角、右下角坐标
        process(matrix,leftRow,leftCol,rightRow,rightCol,list);
        return list;
    }
}

class Question1706{
    int[][] grid;
    public int process(int row,int col){
        if (row== grid.length) return col;//底部掉出
        if (col+1<grid[0].length&&grid[row][col]==1&&grid[row][col+1]==-1) return -1;//向右卡住
        if (grid[row][col]==1&&col== grid[0].length-1) return -1;//向右边界卡住
        if (col-1>=0&&grid[row][col]==-1&&grid[row][col-1]==1) return -1;//向左卡住
        if (grid[row][col]==-1&&col==0) return -1;//向左边界卡住
        int result=0;
        if (grid[row][col]==1) result=process(row+1,col+1);//右滑动
        else if (grid[row][col]==-1) result=process(row+1,col-1);//左滑动
        return result;
    }
    public int[] findBall(int[][] grid) {
        this.grid=grid;
        int[] result=new int[grid[0].length];
        for (int i=0;i< result.length;i++){
            int temp=process(0,i);
            result[i]=temp;
        }
        return result;
    }
}

class Question14{
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0)
            return "";
        String ans = strs[0];
        for(int i =1;i<strs.length;i++) {
            int j=0;
            for(;j<ans.length() && j < strs[i].length();j++) {
                if(ans.charAt(j) != strs[i].charAt(j))
                    break;
            }
            ans = ans.substring(0, j);
            if(ans.equals(""))
                return ans;
        }
        return ans;
    }
}

class Question43{
    public String multiply(String num1, String num2) {
        int length1=num1.length(),length2=num2.length(),index=0;
        char[] str1=num1.toCharArray(),str2=num2.toCharArray();
        int[] ans=new int[length1+length2];
        while (index<length1+length2){
            for (int i=0;i<length1;i++){
                for (int j=0;j<length2;j++){
                    if ((length1-1-i)+(length2-1-j)==index) ans[index]+=(str1[i]-'0')*(str2[j]-'0');
                }
            }
            if (ans[index]>9){//进位
                ans[index+1]+=ans[index]/10;
                ans[index]=ans[index]%10;
            }
            index++;
        }
        StringBuffer result=new StringBuffer();
        boolean flag=true;
        for (int i=length1+length2-1;i>=0;i--){
            if (flag&&ans[i]==0) continue;
            else {
                flag=false;
                result.append(ans[i]);
            }
        }
        if (result.length()==0) return "0";
        return result.toString();
    }
}

class Question19{
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode virtual=new ListNode();
        virtual.next=head;
        ListNode p1=virtual,p2=head;
        for (int i=0;i<n;i++) p2=p2.next;
        while (p2!=null){
            p1=p1.next;
            p2=p2.next;
        }
        p1.next=p1.next.next;
        return virtual.next;
    }
}

class Question234{
    public boolean isPalindrome(ListNode head) {
        List<Integer> list=new ArrayList<>();
        while (head!=null){
            list.add(head.val);
            head=head.next;
        }
        Integer[] arr=list.toArray(new Integer[0]);
        int length= arr.length;
        for (int i=0;i< length/2;i++){
            if (arr[i]!=arr[length-1-i]) return false;
        }
        return true;
    }
}

class Question328{
    public ListNode oddEvenList(ListNode head) {
        if (head==null||head.next==null) return head;
        ListNode odd=head,even=head.next,evenHead=even;
        while (odd!=null&&even!=null&&odd.next!=null&&even.next!=null){
            odd.next=odd.next.next;
            even.next=even.next.next;
            odd=odd.next;
            even=even.next;
        }
        odd.next=evenHead;
        return head;
    }
}

class Question148{
    public ListNode sortList(ListNode head) {
        ListNode now=head;
        List<Integer> list=new ArrayList<>();
        while (now!=null){
            list.add(now.val);
            now=now.next;
        }
        Integer[] arr=list.toArray(new Integer[0]);
        Arrays.sort(arr, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });
        now=head;
        for (int i=0;i< arr.length;i++){
            now.val=arr[i];
            now=now.next;
        }
        return head;
    }
}

class Question2131{
    public int longestPalindrome(String[] words) {
        int maxLength=0;
        boolean flag=false;
        Map<String,Integer> map=new HashMap<>();
        for (String word:words) map.put(word,map.getOrDefault(word,0)+1);
        for (String key:map.keySet()){
            String reverse=new StringBuffer(key).reverse().toString();//回文串单词对称
            if (key.equals(reverse)){
                if (map.get(key)%2==0) maxLength+=map.get(key)*2;
                else {
                    if (map.get(key)==1&&!flag) {
                        maxLength+=2;
                        flag=true;
                    }else if (map.get(key)>1) {
                        maxLength+=(map.get(key)-1)*2;
                        if (flag==false) {
                            maxLength+=2;
                            flag=true;
                        }
                    }
                }
            }
            else if (map.containsKey(reverse)&&!key.contains(reverse)) maxLength+=2*Math.min(map.get(key),map.get(reverse));
        }
        return maxLength;
    }
}

class Question621{
    public int leastInterval(char[] tasks, int n) {
        int[] counts = new int[26];
        for (char c : tasks) counts[c - 'A']++;
        int max = 0, tot = 0;
        for (int i = 0; i < 26; i++) max = Math.max(max, counts[i]);
        for (int i = 0; i < 26; i++) tot += max == counts[i] ? 1 : 0;
        return Math.max(tasks.length, (n + 1) * (max - 1) + tot);
    }
}